#include<vector>
using namespace std;


class Solution {
private:
    vector<vector<int>> rects;
    vector<int> sums;

public:
    Solution(vector<vector<int>>& rects):rects(rects),sums(rects.size()){
        for (int i = 0; i < rects.size(); ++i) {
            sums[i] = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            if (i != 0)
                sums[i] += sums[i - 1];
        }
    }

    vector<int> pick() {
        int index = rand() % sums.back() + 1;
        int left = 0, right = sums.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (sums[mid] == index) {
                left = mid;
                break;
            }
            if (sums[mid] > index)
                right = mid - 1;
            else
                left = mid + 1;
        }
        if (left != 0)
            index -= sums[left - 1];
        index -= 1;
        vector<int> res(2);
        res[0] = index / (rects[left][3] - rects[left][1]+1) + rects[left][0];
        res[1] = index % (rects[left][3] - rects[left][1]+1) + rects[left][1];
        return res;

    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */